// 给定两个正序数组nums1，nums2，找出并返回这两个正序数组的中位数，算法的时间复杂度应该为O(log(m+n))

// 思路：二分查找，两个有序数组的长度分别为m，n，其中位数是第 k = Math.floor((m + n + 1) / 2)个数
// 需要从数组1中取m1个，数组2中取 m2 = k - m1
// 二分比较的关键就是数组1和数组2分割后，左边数组的最大值leftMaxVal = Math.max(arr1[m1-1], arr2[m2-1])
// 和右边数组的最小值rightMinVal = Math.min(arr1[m1], arr2[m2])，leftMaxVal <= rightMinVal
// 如果 arr1[m1] < arr2[m2 - 1],则m1取值太小，移动left

// 时间复杂度：O(log(m+n))
// 空间复杂度：O(1)

function findMedianSortedArrays(arr1, arr2) {
    let len1 = arr1.length
    let len2 = arr2.length
    if (len1 > len2) {
        return findMedianSortedArrays(arr2, arr1)
    }
    let k = Math.floor((len1 + len2 + 1) / 2)
    let left = 0
    let right = len1
    while (left < right) {
        let m1 = Math.floor((right - left) / 2) + left
        let m2 = k - m1
        if (arr1[m1] < arr2[m2 - 1]) {
            left = m1 + 1
        } else {
            right = m1
        }
    }
    let m1 = left
    let m2 = k - left
    let c1 = Math.max(m1 <=0 ? -Infinity : arr1[m1 - 1], m2 <= 0 ? -Infinity : arr2[m2 - 1])
    if ((len1 + len2) % 2 === 1) {
        return c1
    }
    let c2 = Math.min(m1 >= len1 ? Infinity : arr1[m1], m2 >= len2 ? Infinity : arr2[m2])
    return (c1 + c2) / 2
}

let arr1 = [1, 2, 3, 4]
let arr2 = [3, 4, 5, 6, 7]
console.log(findMedianSortedArrays(arr1, arr2));